package com.zp.self.module.level_4_算法练习.算法.二分查找;

/**
 * @author By ZengPeng
 */
public class 力扣_153_寻找旋转排序数组中的最小值 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_153_寻找旋转排序数组中的最小值().findMin(new int[]{3,1,2}));
        System.out.println(new 力扣_153_寻找旋转排序数组中的最小值().findMin(new int[]{2,1}));
        System.out.println(new 力扣_153_寻找旋转排序数组中的最小值().findMin(new int[]{4}));
        System.out.println(new 力扣_153_寻找旋转排序数组中的最小值().findMin(new int[]{4,5}));
        System.out.println(new 力扣_153_寻找旋转排序数组中的最小值().findMin(new int[]{4,5,6,7,0,1,2}));
        System.out.println(new 力扣_153_寻找旋转排序数组中的最小值().findMin(new int[]{1,2,3,5}));
        System.out.println(new 力扣_153_寻找旋转排序数组中的最小值().findMin(new int[]{11,13,15,17}));
    }

    /**
    题目：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
     若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
     若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
     注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
     你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

     示例 1：
     输入：nums = [3,4,5,1,2]
     输出：1
     解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

     示例 2：
     输入：nums = [4,5,6,7,0,1,2]
     输出：0
     解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

     示例 3：
     输入：nums = [11,13,15,17]
     输出：11
     解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

    分析：【P 💕💞💓】
       1.二分查找：比较mid与 nums[0],区分哪边是有序的？
            ----执行用时：0 ms, 在所有 Java 提交中击败了100%的用户
       大神: 比较mid与right

    边界值 & 注意点：
       1.
     **/
    public int findMin(int[] nums) {
        if(nums.length==1) return nums[0];
        int left=0,right=nums.length-1,mid;
        while (left < right) {
            mid= left+(right-left)/2;
            if(nums[mid]<nums[0]){
                right=mid;//这里需要防止：其越过最小值
            }else {
                if(nums[left]<nums[right])//这里要防止：整个数列还是递增的情况
                    right=mid-1;
                else
                    left=mid+1;
            }
        }
        return nums[left];
    }
}
